package leetcode.code0138;

import java.util.HashMap;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.tree.Node;

/**
 * 执行用时：1 ms, 在所有 Java 提交中击败了6.77%的用户
 *
 * 内存消耗：38.2 MB, 在所有 Java 提交中击败了39.73%的用户
 *
 * 通过测试用例：19 / 19
 */
public class Solution2 implements IDebug {

	public Node copyRandomList(Node head) {
		Map<Node, Node> map = new HashMap<>();
		return this.f(head, map);
	}

	private Node f(Node head, Map<Node, Node> map) {
		if (head == null) {
			return null;
		}
		if (map.containsKey(head)) {
			return map.get(head);
		}
		Node node = new Node(head.val);
		map.put(head, node);
		node.random = this.f(head.random, map);
		node.next = this.f(head.next, map);
		return node;
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
